/**
 * 17. 电话号码的字母组合
 *
 * 【中等】
 *
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png
 *
 * 示例 1：
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * 示例 2：
 * 输入：digits = "
 * 输出：[]
 *
 * 示例 3：
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 **/

function letterCombinations(digits: string): string[] {
	if (!digits) return []

	const ans: string[] = []
	const len = digits.length
	const map = new Map()
	map.set('2', 'abc')
	map.set('3', 'def')
	map.set('4', 'ghi')
	map.set('5', 'jkl')
	map.set('6', 'mno')
	map.set('7', 'pqrs')
	map.set('8', 'tuv')
	map.set('9', 'wxyz')

	const dfs = (i, str) => {
		if (i == len) {
			ans.push(str)
			return
		}
		const tmp = map.get(digits[i])
		for (let j = 0; j < tmp.length; j++) {
			dfs(i + 1, str + tmp[j])
		}
	}

	dfs(0, '')

	return ans
}
